import java.util.*;

//数组中两元素的最大乘积(力扣1464)
class Solution {
    public int maxProduct(int[] nums) {
        Arrays.sort(nums);
        return (nums[nums.length-1]-1)*(nums[nums.length-2]-1);
    }
}

//替换后的最长重复字符(力扣424)
class Solution1 {
    public int characterReplacement(String s, int k) {
        int[] count = new int[26]; //用于记录窗口内每个字符的出现次数
        int maxCount = 0; //窗口内出现最多次数的字符的计数
        int maxLength = 0; //最大长度
        int left = 0; //窗口的左指针

        for (int right = 0; right < s.length(); right++) {
            char ch = s.charAt(right);
            count[ch - 'A']++; //更新当前字符的计数
            maxCount = Math.max(maxCount, count[ch - 'A']); //更新窗口内最多字符的计数

            //如果当前窗口大小 - 最多字符的计数 > k，表示需要缩小窗口
            while ((right - left + 1) - maxCount > k) {
                count[s.charAt(left) - 'A']--; //缩小窗口时更新计数
                left++; //移动左指针
            }

            //更新最大长度
            maxLength = Math.max(maxLength, right - left + 1);
        }

        return maxLength;
    }
}

//仅仅反转字母(力扣917)
class Solution2 {
    public String reverseOnlyLetters(String s) {
        char[] chars = s.toCharArray();//将字符串转为字符数组便于操作
        int left = 0, right = s.length() - 1;//左指针和右指针

        while (left < right) {
            //左指针指向非字母，跳过
            if (!Character.isLetter(chars[left])) {
                left++;
            }
            //右指针指向非字母，跳过
            else if (!Character.isLetter(chars[right])) {
                right--;
            }
            //两个指针都指向字母，交换
            else {
                char temp = chars[left];
                chars[left] = chars[right];
                chars[right] = temp;
                left++;
                right--;
            }
        }

        return new String(chars); //将字符数组转换回字符串
    }
}

//LCR 017. 最小覆盖子串
class Solution3 {
    public String minWindow(String s, String t) {
        int n = t.length(), m = s.length();
        //目标字符串比s字符串长
        if (n > m) return "";
        int[] cnt = new int[58]; // 用于记录字符频率（目标t字符串的）
        //为负数的是t字符串中的字母，为0则不是(只有负数和零)
        for (int i = 0; i < n; i++) {
            cnt[t.charAt(i) - 'A']--;
        }
        //count作为记录含有t字符串的字符数,start作为窗口的起始点
        //minlen为最小的窗口长度,先以最大值作为初始值
        //left也是窗口的左临界点，但是后期会通过left++缩小窗口的长度
        int count = 0, start = 0, minLen = Integer.MAX_VALUE;
        int left = 0;

        for (int right = 0; right < m; right++) {
            //如果是目标字符串中的字母就count++,注意:这里就算条件为false，也是会执行cnt[s.charAt(right) - 'A']++,也就是说及时不是t字符串中的字符也会++
            if (cnt[s.charAt(right) - 'A']++ < 0) count++;
            //直到count的长度为t字符串的长度，说明当前窗口包含了t字符串中的所有字母,进入循环
            while (count == n) {
                //当前窗口长度比minlen小,就让minlen等于当前窗口长度
                //然后将起始点作为窗口的left
                if (right - left + 1 < minLen) {
                    minLen = right - left + 1;
                    start = left;
                }
                //由于上面的注意点，不属于t字符串中的字符为正数，属于t字符串的字符为0，
                //还有这里是先--才进行比较，++是执行完条件语句才进行
                if (--cnt[s.charAt(left++) - 'A'] < 0) count--;
            }
        }

        return minLen == Integer.MAX_VALUE ? "" : s.substring(start, start + minLen);
    }
}


